package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    //N皇后
    static class Solution {
        private boolean[] col;      // 列是否被占
        private boolean[] diag1;    // 主对角 r + c 是否被占，长度 2n-1
        private boolean[] diag2;    // 副对角 r - c + (n-1) 是否被占，长度 2n-1
        private List<List<String>> ans;
        private char[][] board;
        private int n;

        public List<List<String>> solveNQueens(int _n) {
            n = _n;
            col = new boolean[n];
            diag1 = new boolean[2 * n ];
            diag2 = new boolean[2 * n ];
            ans = new ArrayList<>();
            board = new char[n][n];
            for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
            dfs(0); // 从第 0 行开始放
            return ans;
        }

        private void dfs(int r) {
            if (r == n) { // 放满 n 行，收集答案
                List<String> cur = new ArrayList<>(n);
                for (int i = 0; i < n; i++) cur.add(new String(board[i]));
                ans.add(cur);
                return;
            }
            for (int c = 0; c < n; c++) {
                int id1 = r + c;
                int id2 = r - c + n;
                if (col[c] || diag1[id1] || diag2[id2]) continue; // 列/对角线冲突

                // 选择
                board[r][c] = 'Q';
                col[c] = diag1[id1] = diag2[id2] = true;

                dfs(r + 1); // 下一行

                // 回退
                board[r][c] = '.';
                col[c] = diag1[id1] = diag2[id2] = false;
            }
        }
    }

    //有效的数独
    static class Solution2 {
        boolean[][] row, col;
        boolean[][][] grid;

        public boolean isValidSudoku(char[][] board) {
            row = new boolean[9][10];
            col = new boolean[9][10];
            grid = new boolean[3][3][10];

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char ch = board[i][j];
                    if (ch == '.') continue;

                    int cur = ch - '0';       // 1~9
                    int gi = i / 3, gj = j / 3;

                    if (row[i][cur] || col[j][cur] || grid[gi][gj][cur]) {
                        return false;         // 冲突：行/列/宫格已有相同数字
                    }

                    row[i][cur] = true;
                    col[j][cur] = true;
                    grid[gi][gj][cur] = true;
                }
            }
            return true;  // 未发现冲突
        }
    }
}
